

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;light&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="https://cdn.jsdelivr.net/gh/kzwrime/kzwrime.github.io/img/favicon.png">
  <link rel="icon" type="image/png" href="https://tuchuangrrr.oss-cn-shenzhen.aliyuncs.com/img/kunnan.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="霜华">
  <meta name="keywords" content="">
  <title>几个搜索技术 - kunzh</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atelier-lakeside-dark.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_pf9vaxs7x7b.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
</head>


<body>
  <header style="height: 60vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>kunzh</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/shuoshuo2/">
                <i class="iconfont icon-speakernotes"></i>
                留言板
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('https://rainrime.top/img/SloveniaAlps.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-09-24 19:40" pubdate>
        2020年9月24日 晚上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      1.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      21
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">几个搜索技术</h1>
            
            <div class="markdown-body" id="post-body">
              <h1 id="搜索技术"><a class="markdownIt-Anchor" href="#搜索技术"></a> 搜索技术</h1>
<p>本文讲述几个常见的问题：全排列问题、子集问题、八数码问题…</p>
<h2 id="递归和排列"><a class="markdownIt-Anchor" href="#递归和排列"></a> 递归和排列</h2>
<blockquote>
<p>问题描述：打印 (0,1,2 … n-1) 共 n 个数的全排列，且返回全排列个数</p>
</blockquote>
<ul>
<li>范例：</li>
</ul>
<pre><code class="hljs angelscript">input: <span class="hljs-number">3</span>
output: 
<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">2</span>
<span class="hljs-number">0</span>,<span class="hljs-number">2</span>,<span class="hljs-number">1</span>
<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">2</span>
<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">0</span>
<span class="hljs-number">2</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>
<span class="hljs-number">2</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>
<span class="hljs-number">6</span></code></pre>
<h4 id="用-stl-输出全排列"><a class="markdownIt-Anchor" href="#用-stl-输出全排列"></a> 用 STL 输出全排列</h4>
<p>利用<code>STL</code>库函数<code>next_permutation()</code>，其按字典序输出下一个排列（使用前应使得数据有序）</p>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;algorithm&gt;	// 使用 sort() 和 next_permutation()</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">full_permutation</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>&#123;
    <span class="hljs-function"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">all_nums</span><span class="hljs-params">(n)</span></span>;
    <span class="hljs-keyword">int</span> count = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;n; i++) all_nums[i] = i;	<span class="hljs-comment">// 初始化数组</span>
    <span class="hljs-keyword">do</span>&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;n; i++) <span class="hljs-built_in">cout</span> &lt;&lt; all_nums[i] &lt;&lt; <span class="hljs-string">&quot;,&quot;</span>;
        <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
        count++;
    &#125;<span class="hljs-keyword">while</span>(next_permutation(all_nums.begin(), all_nums.end()));
    <span class="hljs-keyword">return</span> count;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    <span class="hljs-built_in">cout</span> &lt;&lt; full_permutation(n) &lt;&lt; <span class="hljs-built_in">endl</span>;
&#125;</code></pre>
<h4 id="递归打印全排列"><a class="markdownIt-Anchor" href="#递归打印全排列"></a> 递归打印全排列</h4>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-keyword">int</span> tcount;
<span class="hljs-keyword">int</span> nsize;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; all_nums;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">perm</span><span class="hljs-params">(<span class="hljs-keyword">int</span> begin, <span class="hljs-keyword">int</span> end)</span></span>&#123;
    <span class="hljs-keyword">if</span>(begin == end)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;nsize; i++) <span class="hljs-built_in">cout</span> &lt;&lt; all_nums[i] &lt;&lt; <span class="hljs-string">&quot;,&quot;</span>;
        <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
        tcount++;
    &#125;
    <span class="hljs-keyword">else</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=begin; i&lt;=end; i++)&#123;
            swap(all_nums[begin], all_nums[i]);
            perm(begin+<span class="hljs-number">1</span>, end);
            swap(all_nums[begin], all_nums[i]);
        &#125;
    <span class="hljs-keyword">return</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">full_permutation</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>&#123;
    all_nums = <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;n; i++) all_nums[i] = i;	<span class="hljs-comment">// 初始化数组</span>
    perm(<span class="hljs-number">0</span>, n<span class="hljs-number">-1</span>);
    <span class="hljs-keyword">return</span> tcount;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    tcount = <span class="hljs-number">0</span>;
    <span class="hljs-built_in">cin</span> &gt;&gt; nsize;
    <span class="hljs-built_in">cout</span> &lt;&lt; full_permutation(nsize) &lt;&lt; <span class="hljs-built_in">endl</span>;
&#125;</code></pre>
<h4 id="复杂度"><a class="markdownIt-Anchor" href="#复杂度"></a> 复杂度</h4>
<p>显然全排列复杂度为 O(n!)，上述两个均是。</p>
<p>一般来说，按照每秒千万次计算的估计，限制 1s 时仅要求计算 n &lt;= 11 的情况。</p>
<h2 id="子集的生成和组合问题"><a class="markdownIt-Anchor" href="#子集的生成和组合问题"></a> 子集的生成和组合问题</h2>
<h3 id="问题1"><a class="markdownIt-Anchor" href="#问题1"></a> 问题1</h3>
<blockquote>
<p>问题描述：求包含 n 个元素的集合的幂集（假设 n &lt; 30）</p>
</blockquote>
<ul>
<li>注：幂集为集合，输出不要求顺序。原集合序列第 i 个元素在当前子集中则输出其下标 i 。如 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><msub><mi>a</mi><mn>0</mn></msub><mo separator="true">,</mo><msub><mi>a</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>a</mi><mn>2</mn></msub><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{a_0, a_1, a_2\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">}</span></span></span></span> 的一个子集 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo stretchy="false">{</mo><msub><mi>a</mi><mn>0</mn></msub><mo separator="true">,</mo><msub><mi>a</mi><mn>2</mn></msub><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{a_0, a_2\}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">}</span></span></span></span> 记为 <code>0 2</code>。</li>
<li>范例：</li>
</ul>
<pre><code class="hljs yaml"><span class="hljs-attr">input:</span> <span class="hljs-number">3</span>
<span class="hljs-attr">output:</span> 
<span class="hljs-number">0</span> 
<span class="hljs-number">1</span> 
<span class="hljs-number">0</span> <span class="hljs-number">1</span> 
<span class="hljs-number">2</span> 
<span class="hljs-number">0</span> <span class="hljs-number">2</span> 
<span class="hljs-number">1</span> <span class="hljs-number">2</span> 
<span class="hljs-number">0</span> <span class="hljs-number">1</span> <span class="hljs-number">2</span></code></pre>
<h4 id="基础位运算处理"><a class="markdownIt-Anchor" href="#基础位运算处理"></a> 基础位运算处理</h4>
<p>利用二进制数的特性，定义一个表示：对于二进制数 n ，若 n 的第 i 位（从低到高数）为 1，则原集合序列的第 i 个元素在当前子集中。</p>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">print_subset</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;(<span class="hljs-number">1</span>&lt;&lt;n); i++)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>; j&lt;n; j++)
            <span class="hljs-keyword">if</span>(i &amp; (<span class="hljs-number">1</span>&lt;&lt;j))
                <span class="hljs-built_in">cout</span> &lt;&lt; j &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
        <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
    &#125;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    print_subset(n);
&#125;</code></pre>
<h3 id="问题2"><a class="markdownIt-Anchor" href="#问题2"></a> 问题2</h3>
<blockquote>
<p>问题描述：求包含 n 个元素的集合的所有大小为k的子集（假设 n &lt; 30）</p>
</blockquote>
<ul>
<li>范例：</li>
</ul>
<pre><code class="hljs yaml"><span class="hljs-attr">input:</span> <span class="hljs-number">4</span> <span class="hljs-number">2</span>
<span class="hljs-attr">output:</span> 
<span class="hljs-number">0</span> <span class="hljs-number">1</span> 
<span class="hljs-number">0</span> <span class="hljs-number">2</span> 
<span class="hljs-number">1</span> <span class="hljs-number">2</span> 
<span class="hljs-number">0</span> <span class="hljs-number">3</span> 
<span class="hljs-number">1</span> <span class="hljs-number">3</span> 
<span class="hljs-number">2</span> <span class="hljs-number">3</span></code></pre>
<h4 id="进阶位运算处理"><a class="markdownIt-Anchor" href="#进阶位运算处理"></a> 进阶位运算处理</h4>
<p>当然可以直接用前文的方法数二进制数 n 中 1 的个数，但还用更快的方法：<code>n = n &amp; (n - 1)</code> 其作用为消除 n 二进制表示的最后一个 1。例：</p>
<p>1011 &amp; (1011 - 1) = 1011 &amp; 1010 = 1010</p>
<p>1010 &amp; (1010 - 1) = 1010 &amp; 1001 = 1000</p>
<p>1000 &amp; (1000 - 1) = 1000 &amp; 0111 = 0000</p>
<pre><code class="hljs c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">print_subset</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> k)</span></span>&#123;
	<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i&lt;(<span class="hljs-number">1</span>&lt;&lt;n); i++)&#123;
        <span class="hljs-keyword">int</span> num=<span class="hljs-number">0</span>, kk=i;
        <span class="hljs-keyword">while</span>(kk)&#123;
            kk = kk&amp;(kk<span class="hljs-number">-1</span>);
            num++;
        &#125;
        <span class="hljs-keyword">if</span>(num == k)&#123;
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>; j&lt;n; j++)
                <span class="hljs-keyword">if</span>(i&amp;(<span class="hljs-number">1</span>&lt;&lt;j))
                    <span class="hljs-built_in">cout</span> &lt;&lt; j &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
            <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>;
        &#125;
    &#125;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> n, k;
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; k;
    print_subset(n, k);
&#125;</code></pre>
<h2 id="八数码问题"><a class="markdownIt-Anchor" href="#八数码问题"></a> 八数码问题</h2>
<blockquote>
<p>如图，在一个3*3的棋盘上放置编号为1~8的8个方块，另外还有一个空方块，完成：</p>
<ol>
<li>指定初始棋局和目标棋局，计算出最少的移动步数</li>
<li>输出数码的移动序列（本题不演示）</li>
</ol>
</blockquote>
<pre><code class="hljs gherkin">-------------                -------------
|<span class="hljs-string"> 1 </span>|<span class="hljs-string"> 2 </span>|<span class="hljs-string"> 3 </span>|<span class="hljs-string">                </span>|<span class="hljs-string"> 1 </span>|<span class="hljs-string">   </span>|<span class="hljs-string"> 3 </span>|
-------------                -------------
|<span class="hljs-string">   </span>|<span class="hljs-string"> 8 </span>|<span class="hljs-string"> 4 </span>|<span class="hljs-string">    ------&gt;&gt;    </span>|<span class="hljs-string"> 8 </span>|<span class="hljs-string"> 2 </span>|<span class="hljs-string"> 4 </span>|
-------------                -------------
|<span class="hljs-string"> 7 </span>|<span class="hljs-string"> 6 </span>|<span class="hljs-string"> 5 </span>|<span class="hljs-string">                </span>|<span class="hljs-string"> 7 </span>|<span class="hljs-string"> 6 </span>|<span class="hljs-string"> 5 </span>|
-------------                -------------</code></pre>
<ul>
<li>案例</li>
</ul>
<pre><code class="hljs yaml"><span class="hljs-attr">input:</span>
<span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">0</span> <span class="hljs-number">8</span> <span class="hljs-number">4</span> <span class="hljs-number">7</span> <span class="hljs-number">6</span> <span class="hljs-number">5</span>
<span class="hljs-number">1</span> <span class="hljs-number">0</span> <span class="hljs-number">3</span> <span class="hljs-number">8</span> <span class="hljs-number">2</span> <span class="hljs-number">4</span> <span class="hljs-number">7</span> <span class="hljs-number">6</span> <span class="hljs-number">5</span>
<span class="hljs-attr">output:</span>
<span class="hljs-number">2</span></code></pre>
<h4 id="bfs-状态图搜索-康托展开判重"><a class="markdownIt-Anchor" href="#bfs-状态图搜索-康托展开判重"></a> BFS 状态图搜索 + 康托展开判重</h4>
<p>把一个棋局看作一个状态图，共<code>9!=362880</code> 个状态，每一个状态可以转移为相邻状态，即空格与相邻方块换位置。</p>
<p>需要注意的是，某个状态转移为其他状态可能会回到之前到访过的状态，因此需要快速判定重复。本法使用康托展开(Cantor Expansion) 来判重。</p>
<p>康托展开是一种特殊的哈希函数，本题中，康拓展开实现了以下的映射：</p>
<table>
<thead>
<tr>
<th>状态</th>
<th>012345678</th>
<th>012345687</th>
<th>012345768</th>
<th>…</th>
<th>876543210</th>
</tr>
</thead>
<tbody>
<tr>
<td>Cantor</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>…</td>
<td>9! - 1 = 362879</td>
</tr>
</tbody>
</table>
<p>以一例子说明其原理为：判断<code>2143</code>是·{1，2，3，4}的全排列中的第几个数。</p>
<ol>
<li>计算首位小于2的所有排列，即<code>1xxx</code>，共<code>1*3!=6</code>种。</li>
<li>计算首位为2，第二位小于1的所有排列，即<code>1cxx</code>，c&lt;1。共<code>0*2!=0</code>种。</li>
<li>计算首位为21，第三位小于4的所有排列，即<code>21cx</code>，c&lt;4。共<code>1*1!=1</code>种。</li>
<li>计算首位为213，第四位小于4的所有排列，共<code>0*0!</code>种。</li>
</ol>
<p>故所求为：<code>1*3! + 0*2! + 1*1! + 0*0! = 7</code>。（从0开始数，应为全排列第8个）</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>X</mi><mo>=</mo><mi>a</mi><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>×</mo><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">!</mo><mtext> </mtext><mo>+</mo><mi>a</mi><mo stretchy="false">[</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo><mo>×</mo><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>2</mn><mo stretchy="false">)</mo><mo stretchy="false">!</mo><mtext> </mtext><mo>+</mo><mtext> </mtext><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><mspace linebreak="newline"></mspace><mo>+</mo><mtext> </mtext><mi>a</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>×</mo><mo stretchy="false">(</mo><mi>i</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">!</mo><mtext> </mtext><mo>+</mo><mtext> </mtext><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><mi mathvariant="normal">.</mi><mtext> </mtext><mo>+</mo><mtext> </mtext><mi>a</mi><mo stretchy="false">[</mo><mn>2</mn><mo stretchy="false">]</mo><mo>×</mo><mn>1</mn><mo stretchy="false">!</mo><mtext> </mtext><mo>+</mo><mtext> </mtext><mi>a</mi><mo stretchy="false">[</mo><mn>1</mn><mo stretchy="false">]</mo><mo>×</mo><mn>0</mn><mo stretchy="false">!</mo></mrow><annotation encoding="application/x-tex">X=a[n] \times (n-1)!\ + a[n-1] \times (n-2)!\ +\ ...\\ +\ a[i] \times (i-1)!\ +\ ...\ +\ a[2] \times 1!\ +\ a[1] \times 0!
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.07847em;">X</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">a</span><span class="mopen">[</span><span class="mord mathdefault">n</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mclose">!</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">a</span><span class="mopen">[</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">2</span><span class="mclose">)</span><span class="mclose">!</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span></span><span class="base"><span class="strut" style="height:0.10556em;vertical-align:0em;"></span><span class="mord">.</span><span class="mord">.</span><span class="mord">.</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="mspace newline"></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">a</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mclose">!</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord">.</span><span class="mord">.</span><span class="mord">.</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">a</span><span class="mopen">[</span><span class="mord">2</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.77777em;vertical-align:-0.08333em;"></span><span class="mord">1</span><span class="mclose">!</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mspace"> </span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">a</span><span class="mopen">[</span><span class="mord">1</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord">0</span><span class="mclose">!</span></span></span></span></span></p>
<p>其中，<code>a[i]</code>为当前未出现的元素排在第几个（从0开始），且满足 0 &lt;= a[i] &lt; i (1 &lt;= i &lt;= n).</p>
<p>康托展开可参考：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/39377593">https://zhuanlan.zhihu.com/p/39377593</a></p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/tags/c/">c++</a>
                    
                  </div>
                
              </div>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/09/%E7%BA%BF%E6%80%A7%E6%97%B6%E9%97%B4%E6%8E%92%E5%BA%8F/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">线性时间排序</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/09/%E5%AE%89%E8%A3%85wsl/">
                        <span class="hidden-mobile">wsl 下 c/c++ 安装配置</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: window.location.pathname,
          avatar: "retro",
          meta: ["nick","mail"],
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
        });
      });
    }
    waitElementVisible('vcomments', loadValine);
  </script>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


<!-- 
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          enableQQ: true,
          boolean: true,
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: "window.location.pathname",
          avatar: "retro",
          meta: "["nick","mail"]",
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
            // 设置Bilibili表情包地址
            emojiCDN: '//i0.hdslb.com/bfs/emote/', 
            // 表情title和图片映射
            emojiMaps: {
            "tv_doge": "6ea59c827c414b4a2955fe79e0f6fd3dcd515e24.png",
            "tv_亲亲": "a8111ad55953ef5e3be3327ef94eb4a39d535d06.png",
            "tv_偷笑": "bb690d4107620f1c15cff29509db529a73aee261.png",
            "tv_再见": "180129b8ea851044ce71caf55cc8ce44bd4a4fc8.png",
            "tv_冷漠": "b9cbc755c2b3ee43be07ca13de84e5b699a3f101.png",
            "tv_发怒": "34ba3cd204d5b05fec70ce08fa9fa0dd612409ff.png",
            "tv_发财": "34db290afd2963723c6eb3c4560667db7253a21a.png",
            "tv_可爱": "9e55fd9b500ac4b96613539f1ce2f9499e314ed9.png",
            "tv_吐血": "09dd16a7aa59b77baa1155d47484409624470c77.png",
            "tv_呆": "fe1179ebaa191569b0d31cecafe7a2cd1c951c9d.png",
            "tv_呕吐": "9f996894a39e282ccf5e66856af49483f81870f3.png",
            "tv_困": "241ee304e44c0af029adceb294399391e4737ef2.png",
            "tv_坏笑": "1f0b87f731a671079842116e0991c91c2c88645a.png",
            "tv_大佬": "093c1e2c490161aca397afc45573c877cdead616.png",
            "tv_大哭": "23269aeb35f99daee28dda129676f6e9ea87934f.png",
            "tv_委屈": "d04dba7b5465779e9755d2ab6f0a897b9b33bb77.png",
            "tv_害羞": "a37683fb5642fa3ddfc7f4e5525fd13e42a2bdb1.png",
            "tv_尴尬": "7cfa62dafc59798a3d3fb262d421eeeff166cfa4.png",
            "tv_微笑": "70dc5c7b56f93eb61bddba11e28fb1d18fddcd4c.png",
            "tv_思考": "90cf159733e558137ed20aa04d09964436f618a1.png",
            "tv_惊吓": "0d15c7e2ee58e935adc6a7193ee042388adc22af.png",
            "tv_打脸": "56ab10b624063e966bfcb76ea5dc4794d87dfd47.png",
            "tv_抓狂": "fe31c08edad661d63762b04e17b8d5ae3c71a757.png",
            "tv_抠鼻": "c666f55e88d471e51bbd9fab9bb308110824a6eb.png",
            "tv_斜眼笑": "911f987aa8bc1bee12d52aafe62bc41ef4474e6c.png",
            "tv_无奈": "ea8ed89ee9878f2fece2dda0ea8a5dbfe21b5751.png",
            "tv_晕": "5443c22b4d07fb1907ccc610c8e6db254f2461b7.png",
            "tv_流汗": "cead1c351ab8d79e9f369605beb90148db0fbed3.png",
            "tv_流泪": "7e71cde7858f0cd50d74b0264aa26db612a8a167.png",
            "tv_流鼻血": "c32d39db2737f89b904ca32700d140a9241b0767.png",
            "tv_点赞": "f85c354995bd99e28fc76c869bfe42ba6438eff4.png",
            "tv_生气": "26702dcafdab5e8225b43ffd23c94ac1ff932654.png",
            "tv_生病": "8b0ec90e6b86771092a498c54f09fc94621c1900.png",
            "tv_疑问": "0793d949b18d7be716078349c202c15ff166f314.png",
            "tv_白眼": "c1d59f439e379ee50eef488bcb5e5378e5044ea4.png",
            "tv_皱眉": "72ccad6679fea0d14cce648b4d818e09b8ffea2d.png",
            "tv_目瞪口呆": "0b8cb81a68de5d5365212c99375e7ace3e7891b7.png",
            "tv_睡着": "8b196675b53af58264f383c50ad0945048290b33.png",
            "tv_笑哭": "1abc628f6d4f4caf9d0e7800878f4697abbc8273.png",
            "tv_腼腆": "89712c0d4af73e67f89e35cbc518420380a7f6f4.png",
            "tv_色": "61822c7e9aae5da76475e7892534545336b23a6f.png",
            "tv_调侃": "4bc022533ef31544ca0d72c12c808cf4a1cce3e3.png",
            "tv_调皮": "b9c41de8e82dd7a8515ae5e3cb63e898bf245186.png",
            "tv_鄙视": "6e72339f346a692a495b123174b49e4e8e781303.png",
            "tv_闭嘴": "c9e990da7f6e93975e25fd8b70e2e290aa4086ef.png",
            "tv_难过": "87f46748d3f142ebc6586ff58860d0e2fc8263ba.png",
            "tv_馋": "fc7e829b845c43c623c8b490ee3602b7f0e76a31.png",
            "tv_鬼脸": "0ffbbddf8a94d124ca2f54b360bbc04feb6bbfea.png",
            "tv_黑人问号": "45821a01f51bc867da9edbaa2e070410819a95b2.png",
            "tv_鼓掌": "1d21793f96ef4e6f48b23e53e3b9e42da833a0f6.png"
                // ... 更多表情
            }
        });
      });
    }
    createObserver(loadValine, 'vcomments');
  </script>
      <style>
        #vcomments textarea {
            box-sizing: border-box;
            background: url("/img/v2-f3d5c26e7ac0da80ee72b6dc178d6aa1_b005.gif") 100% 100% no-repeat;
        }
      </style>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>
 -->

              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <img src="/img/371905140-ROBOT-WAVING-400px-unscreen(1).gif" srcset="/img/loading.gif" class="rounded mx-auto d-block mt-5" style="width:200px; height:200px;" >
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
        <br>
        <span>©2019 - 2020 By</span>
        <a href="https://github.com/rainrime" target="_blank" rel="nofollow noopener"><span>kunzh</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>


<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "几个搜索技术&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
      icon: "❡"
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- KaTeX -->
    <link  rel="stylesheet" href="https://cdn.staticfile.org/KaTeX/0.11.1/katex.min.css" />
  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/244aa65c.js", 'daovoice');
    daovoice('init', {
      app_id: "244aa65c",
    });
    daovoice('update');
  </script>









  

  

  

  

  

  





</body>
</html>
